// https://leetcode.com/problems/perfect-squares/description/
// 参考了discussion：https://leetcode.com/problems/perfect-squares/discuss/71488/Summary-of-4-different-solutions-(BFS-DP-static-DP-and-mathematics)
class Solution {
public:
    int numSquares(int n) {
        if (n == 0)
            return 0;
        vector<int> numSquaresVec = {0};
        while (numSquaresVec.size() <= n)
        {
            int size = numSquaresVec.size();
            int result = INT_MAX;
            for (int i = 1; i * i <= size; i++)
                result = min(result, numSquaresVec[size - i * i] + 1);
            numSquaresVec.push_back(result);
        }
        return numSquaresVec[n];
    }
};
